package ljl.alg.wangzheng_camp.round1.dp;

import java.util.Arrays;

/**
 * 上一个是求最小值，这个是求有几种分法，不一样了
 *
 * */
public class _518_coin_change_2 {
    
    /**
     * 这个解法有非常恶心的重复计算，不知道怎么回事
     * 他们说这个出来的是排列数，不是组合数，那为啥下面的是组合数？
     *
     * 自己抠了鸡巴好几个小时，发现底下有很多屄友也有相同的疑问
     *
     * 大概是这个意思：当你以 amount 遍历时，它往前找：-1 行不行？ -2 行不行？都行，加起来
     * 比如当前 3，-1 可以，是 2 + 1；-2 可以，是 1 + 2；这两种是一种情况，重复了
     *
     * 当你以 coin 来遍历，所有金额都是只减一个 coin，不会出现两次的情况，每个金额，对于每个 coin 都只算一次；
     * 上面说的，某个金额，可能正着一次反着一次
     *
     * 去你妈屄的！
     * */
    static class WRONG {
        static public int change(int amount, int[] coins) {
            int[] dp = new int[amount + 1];
            dp[0] = 1;
            Arrays.sort(coins);
            for (int i = coins[0]; i <= amount; i++) {
                for (int coin : coins) {
                    if (i < coin) break;
                    dp[i] += dp[i - coin];
                    // 3 ？ 1 2 ， 2 1？
                }
            }
            return dp[amount];
        }
    
    }
    
    static class dp {
        static public int change(int amount, int[] coins) {
            int[] dp = new int[amount + 1];
            dp[0] = 1;
            for (int coin : coins) {
                for (int i = coin; i <= amount; i++) {
                    dp[i] += dp[i - coin];
                }
            }
            return dp[amount];
        }
    }
    
}
